package top.minuy.structure.map;

import top.minuy.structure.linear.array.Array;


/**
 * 基于AVL树的映射
 *
 * @param <K> key
 * @param <V> val
 * @author Minuy
 * @time 18:54
 * @date 2021/11/4
 */
public class AVLTreeMap<K extends Comparable<K>, V> implements Map<K, V> {

    /**
     * 二叉树节点
     */
    class Node {
        // 元素
        public K key;
        public V val;
        // 左右节点
        public Node left, right;
        // 树当前的高度
        int height;

        public Node(K key, V val) {
            this(key, val, null, null, 1);
        }

        public Node(K key, V val, Node left, Node right, int height) {
            this.key = key;
            this.val = val;
            this.left = left;
            this.right = right;
            this.height = height;
        }
    }

    private Node root;
    private int size;

    public AVLTreeMap() {
        root = null;
        size = 0;
    }

    /**
     * 用于辅助遍历Key
     */
    class KeyQueue {
        private Object[] queue;

        private int size;

        public KeyQueue(int capacity) {
            queue = new Object[capacity];
            size = 0;
        }

        public void enQueue(Object key) {
            queue[size] = key;
            size++;
        }

        public Object[] getQueue() {
            return queue;
        }
    }

    /**
     * 返回所有键
     *
     * @return 键数组
     */
    public Object[] getKeyArray() {
        KeyQueue queue = new KeyQueue(size);
        preOrder(root, queue);
        return queue.getQueue();
    }

    private void preOrder(Node node, KeyQueue queue) {
        if (node == null) {
            return;
        }
        queue.enQueue(node.key);
        preOrder(node.left, queue);
        preOrder(node.right, queue);
    }


    /**
     * 获取目标结点高度
     *
     * @param node 目标结点
     * @return 目标结点高度值
     */
    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    /**
     * 判断这棵树是不是二分搜索树
     *
     * @return 是/不是
     */
    public boolean isBST() {
        Array<K> keys = new Array<>(size);
        inOrder(root, keys);
        for (int i = 1; i < keys.getSize(); i++) {
            if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 为isBST()服务，中序遍历，放在Array中
     *
     * @param node  遍历开始的结点
     * @param array 数组
     */
    private void inOrder(Node node, Array<K> array) {
        if (node == null) {
            return;
        }
        inOrder(node.left, array);
        array.addLast(node.key);
        inOrder(node.right, array);
    }

    /**
     * 判断一棵树是不是平衡二叉树
     *
     * @return 是/不是
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    /**
     * 判断是否是平衡二叉树，递归
     *
     * @param node 判断的树的根
     * @return 是/不是
     */
    private boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }
        // 如果平衡因子的绝对值大于1，则不是平衡二叉树
        if (Math.abs(getBalanceFactor(node)) > 1) {
            return false;
        }
        return isBalanced(node.right) && isBalanced(node.left);
    }

    /**
     * 计算当前节点的平衡因子
     *
     * @param node 要计算的节点
     * @return 平衡因子（左右子树高度差）
     */
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 对结点y进行右旋转操作，返回旋转后新的根节点x
     *
     * @return 旋转后的根节点 x
     */
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T3 = x.right;

        x.right = y;
        y.left = T3;

        // 更新高度，不要忘记加一
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        return x;
    }

    /**
     * 对结点y进行左旋转操作，返回旋转后新的根节点x
     *
     * @return 旋转后的根节点 x
     */
    private Node leftRotate(Node y) {
        Node x = y.right;
        Node T2 = x.left;

        x.left = y;
        y.right = T2;

        // 更新高度，不要忘记加一
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        return x;
    }

    private Node add(Node node, K key, V val) {
        if (node == null) {
            size++;
            return new Node(key, val);
        } else if (key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, val);
            // 这里并没有新增任何元素
            //size++;
        } else if (key.compareTo(node.key) < 0) {
            node.left = add(node.left, key, val);
            // 这里并没有新增任何元素
            //size++;
        }

        // ++++++++AVL计算当前节点高度+++++++++++
        node.height = 1 + (Math.max(getHeight(node.right), getHeight(node.left)));
        // System.out.println(node.e+"高度："+node.height);

        int balanceFactor = getBalanceFactor(node);

        // LL
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {// 左侧的左侧 （LL）
            return rightRotate(node);
        }

        // LR
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {// （LR）
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RR
        if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {// 右侧的右侧（RR）
            return leftRotate(node);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { // （RL）
            node.right = rightRotate(node.right); // 转换成RR
            return leftRotate(node);
        }

        // 满足有返回值语法
        return node;
    }


    /**
     * 向字典中添加键值对
     *
     * @param key 键
     * @param val 值
     */
    @Override
    public void add(K key, V val) {
        root = add(root, key, val);
    }

    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }

        Node retNode;

        if (node.key.compareTo(key) > 0) {
            node.left = remove(node.left, key);
            retNode = node;
        } else if (node.key.compareTo(key) < 0) {
            node.right = remove(node.right, key);
            retNode = node;
        } else { // node.key.compareTo(key) == 0
            if (node.left == null) {
                Node t = node.right;
                node.right = null;
                size--;
                retNode = t;
            } else if (node.right == null) {
                Node t = node.left;
                node.left = null;
                size--;
                retNode = t;
            } else {
                // 右子树最小值，或者左子树最大值
                Node minimumNode = getMinimum(node.right);
                node.right = remove(node.right, minimumNode.key);

                minimumNode.left = node.left;
                minimumNode.right = node.right;

                node.right = node.left = null;

                retNode = minimumNode;
            }
        }

        if (retNode == null) {
            return null;
        }

        retNode.height = 1 + (Math.max(getHeight(retNode.right), getHeight(retNode.left)));

        int balanceFactor = getBalanceFactor(retNode);

        // LL
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {// 左侧的左侧 （LL）
            return rightRotate(retNode);
        }

        // LR
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {// （LR）
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }

        // RR
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {// 右侧的右侧（RR）
            return leftRotate(retNode);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { // （RL）
            retNode.right = rightRotate(retNode.right); // 转换成RR
            return leftRotate(retNode);
        }

        return retNode;

    }

    /**
     * 获取这棵树中的最小值
     *
     * @param node 根节点
     * @return 最小值所在的节点
     */
    private Node getMinimum(Node node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node;
        } else {
            return getMinimum(node.left);
        }
    }

    /**
     * 删除一个键值对
     *
     * @param key 要被删除的键
     * @return 返回被删除键的值，如若键不存在，返回空
     */
    @Override
    public V remove(K key) {
        Node retNode = remove(root, key);
        return retNode == null ? null : retNode.val;
    }

    private boolean contains(Node node, K key) {
        if (node == null) {
            return false;
        }

        if (key.compareTo(node.key) < 0) {
            // 小于节点，到左边去找
            return contains(node.left, key);
        } else if (key.compareTo(node.key) > 0) {
            // 大于节点，到右边去找
            return contains(node.right, key);
        }

        return true;
    }


    /**
     * 查询键是否存在
     *
     * @param key 要查询的键
     * @return 此键是否存在
     */
    @Override
    public boolean contains(K key) {
        return contains(root, key);
    }

    private Node get(Node node, K key) {
        if (node == null) {
            return null;
        }

        if (key.compareTo(node.key) > 0) {
            return get(node.right, key);
        } else if (key.compareTo(node.key) < 0) {
            return get(node.left, key);
        }

        return node;
    }

    /**
     * 获取一个键的值
     *
     * @param key 键
     * @return 值
     */
    @Override
    public V get(K key) {
        Node t = get(root, key);
        return t == null ? null : t.val;
    }

    /**
     * 修改一个键值对
     *
     * @param key    键
     * @param newVal 值
     */
    @Override
    public void set(K key, V newVal) {
        Node t = get(root, key);
        if (t == null) {
            throw new IllegalArgumentException("Set failed. Key is not contains.");
        } else {
            t.val = newVal;
        }
    }

    /**
     * 获取字典的大小
     *
     * @return 字典的大小
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断字典是否为空
     *
     * @return 字典是否为空
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}
